package day62_932;

import java.util.HashMap;
import java.util.Map;

/**
 * @ClassName Solution
 * @Description TODO
 * @Author clockTown
 * @Date 2021/7/10 19:24
 * @Version 1.0
 */
public class Solution {
    Map<Integer, int[]> memo;
    public int[] beautifulArray(int n) {
        memo = new HashMap<>();
        memo.put(1, new int[]{1});
        return f(n);
    }

    private int[] f(int n) {
        if (!memo.containsKey(n)){
            int index = 0;
            int[] res = new int[n];
            //将1~(N+1)/2的漂亮数组中的所有整数映射为1~N范围内的奇数
            for (int x : f((n + 1) / 2)){
                res[index++] = 2 * x - 1;
            }
            //将1~N/2的漂亮数组中的所有整数映射为1~N范围内的偶数
            for (int x : f(n / 2)) {
                res[index++] = 2 * x;
            }
            //将合并后的漂亮数组存入memo中
            memo.put(n ,res);
        }
        return memo.get(n);
    }
}
